package 算法模板;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 需求：
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
 * 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lru-cache
 * <p>
 * 最近最少使用算法
 * 思路：
 * 在内存空间有限的情况下，当内存不足时，优先淘汰最久未被使用的数据
 */
public class LRU淘汰算法 {

    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(3);
//        lruCache.put(2, 1);
//        System.out.println(lruCache.get(2));
//        lruCache.put(3, 2);
//        System.out.println(lruCache.get(2));
//        System.out.println(lruCache.get(3));

//        lruCache.put(1, 1);
//        lruCache.put(2, 2);
//        System.out.println(lruCache.get(1));
//        lruCache.put(3, 3);
//        System.out.println(lruCache.get(2));

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        System.out.println(lruCache.get(4));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.get(1));
        lruCache.put(5, 5);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
        System.out.println(lruCache.get(5));

    }

}

/**
 * 定义链表尾部的节点是最近使用的节点，每次访问的元素都放置到尾部节点
 * 那么链表头就是最久未被使用的节点，优先删除
 * 单链表+哈希表
 */
class SingleLinkedLRUCache {

    private int maxCapacity;

    private int curSize = 0;

    private Map<Integer, Node> map = new HashMap<>();

    private Node firstNode;

    private Node lastNode;

    public SingleLinkedLRUCache(int capacity) {
        maxCapacity = capacity;
    }

    // get一次如果有节点，需要放置到尾部
    public int get(int key) {
        Node curNode = map.get(key);
        if (curNode == null) {
            return -1;
        }
        if (curNode.nextNode != null) {  //不是尾部节点
            Node lastNode = new Node(curNode.key, curNode.value);
            remove(curNode);
            addLast(lastNode);
        }
        return lastNode.value;
    }

    public void put(int key, int value) {
        // key是否已经存在
        Node curNode = map.get(key);
        // 不存在，需新增一个key
        if (curNode == null) {
            if (curSize >= maxCapacity) {   //没有容量了，优先淘汰头节点
                // 删除头节点
                remove(firstNode);
            }
        } else {  // 已经存在key，先从链表中删除节点，然后添加当前节点至末尾
            if (curNode.nextNode == null) {  //已经是末尾元素，只需要更新值
                curNode.value = value;
                return;
            }
            remove(curNode);
        }
        addLast(new Node(key, value));
    }

    private void remove(Node curNode) {
        curSize--;
        // 当前节点就是头节点，并且列表中仅一个节点
        if (curNode.nextNode == null) {
            firstNode = null;
            map.remove(curNode.key);
            return;
        }
        map.remove(curNode.key);
        curNode.key = curNode.nextNode.key;
        curNode.value = curNode.nextNode.value;
        curNode.nextNode = curNode.nextNode.nextNode;
        // 需要同步map里面的链表，因为curNode的地址值仍然是要删除的节点，但是key,value,nextNode值变成
        // 了下个节点的，相等于删除了当前节点
        map.put(curNode.key, curNode);
        // 如果当前节点是倒数第二个节点，那么最后一个节点赋值给当前节点，当前节点更新为尾部节点
        if (curNode.nextNode == null) lastNode = curNode;
        if (curSize == 1) {
            lastNode = firstNode;
        }
    }

    private void addLast(Node node) {
        if (firstNode == null) {
            firstNode = node;
            lastNode = node;
            map.put(node.key, node);
            curSize++;
            return;
        }
        // 链表尾部的下个节点改为当前节点
        lastNode.nextNode = node;
        // 当前节点变成最后的节点
        lastNode = node;
        map.put(node.key, node);
        curSize++;
    }

    static class Node {

        // 删除该节点的时候，同步删除map里面的key
        private int key;

        private int value;

        private Node nextNode;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

    }

}


/**
 * 双向链表+哈希表
 * 定义链表头部是最近使用的数据，优先淘汰掉尾部的数据
 * 双向链表的优点: 删除链表中节点的时候，key对应的节点地址值是不会变的
 * 单向链表删除会改变某个地址值的key从而需要同步map中key对应的节点地址值
 */
class LRUCache {

    private int maxCapacity;

    private int curSize;

    // 伪头尾节点head.next为真正的头节点,tail.pre为真正的尾节点
    private DLinked head = new DLinked();

    private DLinked tail = new DLinked();

    private Map<Integer, DLinked> map = new HashMap<>();

    public LRUCache(int capacity) {
        maxCapacity = capacity;
        // 伪头尾节点连接起来，不然会空指针
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DLinked curNode = map.get(key);
        if (curNode == null) {
            return -1;
        }
        moveToHead(curNode);
        return curNode.value;
    }

    public void put(int key, int value) {
        DLinked curNode = map.get(key);
        if (curNode == null) {
            curNode = new DLinked(key, value);
            addHead(curNode);
            map.put(key, curNode);
            if (curSize > maxCapacity) {
                removeTail();
            }
        } else {
            // 需要更新值
            curNode.value = value;
            moveToHead(curNode);
        }
    }

    private void moveToHead(DLinked curNode) {
        // 先从链表中删除该节点
        removeNode(curNode);
        // 添加到头节点
        addHead(curNode);
    }

    // 将当前节点放置到头节点
    private void addHead(DLinked curNode) {
        head.next.pre = curNode;
        curNode.next = head.next;
        head.next = curNode;
        curNode.pre = head;
        curSize++;
    }

    // 从链表中删除节点
    private void removeNode(DLinked curNode) {
        curNode.pre.next = curNode.next;
        curNode.next.pre = curNode.pre;
        curSize--;
    }

    // 从链表尾部删除一个节点，同步删除map中节点
    private void removeTail() {
        DLinked tailNode = tail.pre;
        removeNode(tailNode);
        map.remove(tailNode.key);
    }

    private class DLinked {

        private int key;
        private int value;
        private DLinked pre;
        private DLinked next;

        public DLinked() {
        }

        public DLinked(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }
}

/**
 * 通过继承LinkedHashMap类
 */
class APILRUCache extends LinkedHashMap<Integer, Integer> {

    private int capacity;

    public APILRUCache(int capacity) {
        // accessOrder  false基于插入顺序，true基于访问顺序(get一个元素后，这个元素被加到最后)
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    // Returns <tt>true</tt> if this map should remove its eldest entry.
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

}
